#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

class Solution
{
public:
    int minTimeToReach(vector<vector<int>> &moveTime)
    {
        // Dijsktra
        int n = moveTime.size(), m = moveTime[0].size();
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        dist[0][0] = 0;
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; // {dist, x, y}
        pq.push({0, 0, 0});
        vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!pq.empty())
        {
            auto node = pq.top();
            pq.pop();
            int d = node[0], x = node[1], y = node[2];
            if (x == n - 1 && y == m - 1)
                return d;
            int cost = 1;
            if (d > dist[x][y])
                continue;
            for (auto &dir : dirs)
            {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                int dis = max(d, moveTime[nx][ny]) + cost;
                if (dis < dist[nx][ny])
                {
                    dist[nx][ny] = dis;
                    pq.push({dis, nx, ny});
                }
            }
        }
        return -1;
    }
};

int main()
{

    // system("pause");
    return 0;
}
